package main

import (
	"sort"
	"strconv"
	"strings"
)

// 93. 复原 IP 地址
//
// https://leetcode.cn/problems/restore-ip-addresses/
//
// ```go
func restoreIpAddresses(s string) []string {
	ans := make([][]string, 0)
	var dfs func(path []string, pos int)
	dfs = func(path []string, pos int) {
		if len(path) > 4 {
			return
		}
		if pos == len(s) && len(path) == 4 {
			tmp := make([]string, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
			return
		}
		for i := pos; i < len(s); i++ {
			if cnt, ok := check(s[pos : i+1]); ok {
				path = append(path, cnt)
				dfs(path, i+1)
				path = path[:len(path)-1]
			}
		}
	}
	dfs([]string{}, 0)
	result := make([]string, 0)
	for i := range ans {
		tmp := strings.Join(ans[i], ".")
		result = append(result, tmp)
	}
	return result
}

func check(s string) (string, bool) {
	if s[0] == '0' && len(s) != 1 {
		return "", false
	}
	cnt, _ := strconv.Atoi(s)
	if cnt >= 0 && cnt <= 255 {
		return strconv.Itoa(cnt), true
	}
	return "", false
}

//```

// 78. 子集
//
// https://leetcode.cn/problems/subsets/
//
// ```go
func subsets(nums []int) [][]int {
	ans := make([][]int, 0)
	var dfs func(path []int, pos int)
	dfs = func(path []int, pos int) {
		if true {
			tmp := make([]int, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
		}
		for i := pos; i < len(nums); i++ {
			path = append(path, nums[i])
			dfs(path, i+1)
			path = path[:len(path)-1]
		}
	}
	dfs([]int{}, 0)
	return ans
}

//```

// 90. 子集 II
//
// https://leetcode.cn/problems/subsets-ii/
//
// ```go
func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	ans := make([][]int, 0)
	var dfs func(path []int, pos int)
	dfs = func(path []int, pos int) {
		if true {
			tmp := make([]int, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
		}
		mp := map[int]bool{}
		for i := pos; i < len(nums); i++ {
			if _, ok := mp[nums[i]]; ok {
				continue
			}
			path = append(path, nums[i])
			mp[nums[i]] = true
			dfs(path, i+1)
			path = path[:len(path)-1]
			mp[nums[i]] = false
		}
	}
	dfs([]int{}, 0)
	return ans
}

//```
